package me.mingshan.leetcode;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * https://leetcode.cn/problems/k-closest-points-to-origin
 * <p>
 * K 个最接近原点的点
 * <p>
 * 给定一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点，并且是一个整数 k ，返回离原点 (0,0) 最近的 k 个点。
 * <p>
 * 这里，平面上两点之间的距离是 欧几里德距离（ √(x1 - x2)2 + (y1 - y2)2 ）。
 * <p>
 * 你可以按 任何顺序 返回答案。除了点坐标的顺序之外，答案 确保 是 唯一 的。
 *
 * @author hanjuntao
 * @date 2025/7/3 0003
 */
public class L_973_k_closest_points_to_origin {

    public static void main(String[] args) {
        int[][] points = {{1, 3}, {-2, 2}};
        int[][] result = kClosest(points, 1);
        for (int i = 0; i < result.length; i++) {
            System.out.println(result[i][0] + " " + result[i][1]);
        }

        System.out.println("--------------------------------------------------------------------------");

        int[][] points2 = {{3, 3}, {5, -1}, {-2, 4}};
        int[][] result2 = kClosest(points2, 2);
        for (int i = 0; i < result2.length; i++) {
            System.out.println(result2[i][0] + " " + result2[i][1]);
        }

        System.out.println("--------------------------------------------------------------------------");
        int[][] points3 = {{0, 1}, {1, 0}};
        int[][] result3 = kClosest(points3, 2);
        for (int i = 0; i < result3.length; i++) {
            System.out.println(result3[i][0] + " " + result3[i][1]);
        }

        System.out.println("--------------------------------------------------------------------------");
        int[][] points4 = {{2, 2}, {2, 2}, {3, 3}, {2, -2}, {1, 1}};
        int[][] result4 = kClosest(points4, 4);
        for (int i = 0; i < result4.length; i++) {
            System.out.println(result4[i][0] + " " + result4[i][1]);
        }
    }

    /**
     * 该问题可以转化为 求最小的k个点，即求最小的k个点，并返回这些点
     * <p>
     * 思路：
     * 使用最大堆
     *
     * @param points
     * @param k
     * @return
     */
    public static int[][] kClosest(int[][] points, int k) {
        // key: 坐标(x,y)，value: 距离
        Map<String, Double> map = new HashMap<>();

        for (int i = 0; i < points.length; i++) {
            int x = points[i][0];
            int y = points[i][1];
            int distance = x * x + y * y;
            map.put(x + "," + y, Math.sqrt(distance));
        }

        // 大根堆
        PriorityQueue<Map.Entry<String, Double>> pq = new PriorityQueue<>(k, (o1, o2) -> {
            if (o1.getValue() < o2.getValue()) {
                return 1;
            } else {
                return -1;
            }
        });

        for (int i = 0; i < points.length; i++) {
            int x = points[i][0];
            int y = points[i][1];
            String point = x + "," + y;

            Double distance = map.get(point);
            Map.Entry<String, Double> entry = new Map.Entry<String, Double>() {
                @Override
                public String getKey() {
                    return point;
                }

                @Override
                public Double getValue() {
                    return distance;
                }

                @Override
                public Double setValue(Double value) {
                    return null;
                }
            };

            pq.offer(entry);
            if (pq.size() > k) {
                pq.poll();
            }
        }

        int[][] res = new int[k][2];
        for (int i = k - 1; i >= 0; i--) {
            Map.Entry<String, Double> entry = pq.poll();
            String[] split = entry.getKey().split(",");
            res[i][0] = Integer.parseInt(split[0]);
            res[i][1] = Integer.parseInt(split[1]);
        }

        return res;
    }
}
